home *** CD-ROM | disk | FTP | other *** search
Text File | 1996-05-08 | 10.7 KB | 453 lines | [TEXT/R*ch] |
- /*
- 23 April 1996.
- Submission to MacTech Programmer's challenge for May-96.
- Copyright 1996, Ernst Munter, Kanata, ON, Canada.
-
- "Edge Detector"
-
- Version 3: Uses GetPixBaseAddr() in line 209.
-
- Problem Statement
- -----------------
- Given a Pixmap image, create a Bitmap which shows the edges
- in the image.
-
- Pixmaps may have 8, 16, or 32 bit colors. Parameters control
- which colors should contribute to the edge detection, and a
- threshold for the color space difference (an RMS value) to
- be considered an edge.
-
- All 16 bits of the individual color values must be
- considered, which can result in 32-bit overflow when squares
- are added.
-
- Solution
- --------
- The general idea is to process 2-row strips of the image
- through an intermediate ColorSpec stage in which the
- "value" fields are used to mark edge pixels.
-
- Step1:
-
- We allocate a small amount of memory, sufficient to hold
- two rows of pixels in ColorSpec format (8 bytes per pixel).
- Pixels from each row in the Pixmap are converted to
- ColorSpec format (RGB + "value").
-
- Step2:
-
- The two lines are scanned with 4 different patterns
- to determine edges: given 2 rows with pixels as shown
-
- A B C D E F G H ...
- a b c d e f g h ...
-
- We compare pixel pairs in four separate runs of EdgePairs():
- a-b, b-c, c-d, d-e ... (WEST - EAST)
- A-b, B-c, C-d, D-e ... (NORTH-WEST - SOUTH-EAST)
- B-a, C-b, D-c, E-d ... (NORTH-EAST - SOUTH-WEST)
- A-a, B-b, C-c, D-d ... (NORTH - SOUTH)
-
- This procedure is repeated for rows 0 and 1, then 1 and 2,
- 2 and 3, and so on. (Plus an West-East run for row 0).
-
- During each run, the "value" field of every pair of pixels
- found to be part of an edge is set to -1 (0xFFFF).
- All other values remain at 0.
-
- Step 3:
-
- Before shifting down to the next row, the ColorSpecs
- of the upper row are scanned to construct a row of
- the Bitmap.
-
- Optimizations
- -------------
- The combinations of pixel size and edge types are dealt
- with as follows:
-
- All pixel types are normalized to a single ColorSpec format
- by the GetLine procedure.
-
- Different edge types call for different series of tests.
- Specifically, 1, 2, or 3 colors can be optimized separately.
- On of a set of 7 separate short functions is selected at
- runtime. This requires the edge type to be evaluated only
- once, to select the EdgeXXX procedure that will be used many
- times as the image is scanned from top to bottom.
-
- Comparing an RMS (root of sum of squares) value with a
- threshold is equivalent to comparing the sum of squares
- with the square of the threshold value. This avoids the
- need to compute square roots.
-
- In the case of a single color edge type, the square of the
- difference would not need to be formed. A simple comparison
- of the threshold with the absolute difference would suffice.
- However, the runtime difference between a multiply and
- computing the absolute value would depend on CPU type etc,
- and would tend to be small. I opted for uniformity, and
- square all differences.
-
- The dynamically allocated storage should typically fit
- inside the CPU cache, and not slow things down as it is
- read and written continuously.
-
- Assumptions
- -----------
- Bitmap is large enough to hold the result.
- eType is within the range of redOnly to redGreenAndBlue,
- otherwise the call will certainly crash.
-
- Amount of static memory = 8 pointers (32 bytes)
- Amount of dynamic memory required is for 2 rows of
- ColorSpec records (a 1024 pix wide image -> 16K of storage).
-
- */
-
-
-
- /********************** HEADER INFO **********************/
- // Please use what you need in your environment.
-
- #include "edge.h"
- // Contains PixMap, BitMap and EdgeType defs
-
- #include <stdlib.h>
- /*************** END OF DISPOSABLE HEADER INFO ************/
-
-
- /******************* Definitions **************************/
-
- typedef void EdgeProc(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH);
-
- /******************* Function Prototypes ******************/
- void EdgeDetect(
- PixMapHandle pMapH,
- BitMap *bMap,
- unsigned short threshold,
- EdgeType eType);
-
- void Get1Line(
- ColorSpec* line,
- void* pix,
- int size,
- ColorSpec* CT,
- int pixelSize);
-
- void EdgeRed(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH);
-
- void EdgeGreen(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH);
-
- void EdgeRedGreen(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH);
-
- void EdgeBlue(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH);
-
- void EdgeRedBlue(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH);
-
- void EdgeGreenBlue(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH);
-
- void EdgeRedGreenBlue(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH);
-
- void Copy2Bitmap(
- ColorSpec* P,
- unsigned char* bits,
- int size);
-
- /********************* Static Allocations *****************/
-
- static EdgeProc* EdgeProcedure[8] = {
- 0,
- EdgeRed,
- EdgeGreen,
- EdgeRedGreen,
- EdgeBlue,
- EdgeRedBlue,
- EdgeGreenBlue,
- EdgeRedGreenBlue};
-
- /********************* The EdgeDetect Function ************/
- void EdgeDetect(
- PixMapHandle pMapH,
- BitMap *bMap,
- unsigned short threshold,
- EdgeType eType) {
- PixMap* pm=*pMapH;
- //unsigned char* pix=(unsigned char*)pm->baseAddr;
- unsigned char* pix=(unsigned char*)GetPixBaseAddr(pMapH);
- unsigned char* bits=(unsigned char*)bMap->baseAddr;
- unsigned long TH=(unsigned long)threshold*threshold;
- int y;
- int pixelSize=pm->pixelSize;
- int pixRowBytes=pm->rowBytes & 0x3FFF;
- int pixInRow=pm->bounds.right-pm->bounds.left;
- int bitRowBytes=bMap->rowBytes;
-
- ColorSpec* allocated;
- ColorSpec* line0;
- ColorSpec* line1;
- ColorSpec* CTable=(*(pm->pmTable))->ctTable;
- EdgeProc* EP;
-
- // Get memory for a 2-row strip of pixels:
- if (0==(allocated=(ColorSpec*)malloc(
- 2*sizeof(ColorSpec)*pixInRow))) return;
- line0=allocated-1; //(we always use pre-increment later)
- line1=line0+pixInRow;
-
- // Determine EdgeProc to use:
- EP=EdgeProcedure[eType];
-
- // Prepare first row:
- Get1Line(line0,pix,pixInRow,CTable,pixelSize);
- (*EP)(line0,line0+1,pixInRow-1,TH); //W--E
-
- // Process remaining rows:
- for (y=pm->bounds.top+1;y<pm->bounds.bottom;y++) {
- pix+=pixRowBytes;
- Get1Line(line1,pix,pixInRow,CTable,pixelSize);
-
- (*EP)(line1, line1+1,pixInRow-1,TH); //W--E
- (*EP)(line0, line1+1,pixInRow-1,TH); //NW--SE
- (*EP)(line0+1,line1, pixInRow-1,TH); //NE--SW
- (*EP)(line0, line1, pixInRow,TH); //N--S
-
- // Convert ColorSpec.values to Bitmap.bits:
- Copy2Bitmap(line0,bits,bitRowBytes);
-
- // Swap line0 with line1:
- {ColorSpec* temp=line0;line0=line1;line1=temp;}
- bits+=bitRowBytes;
- }
-
- // Convert the last row;
- Copy2Bitmap(line0,bits,bitRowBytes);
-
- // Release dynamic memory:
- free(allocated);
- }
-
- /***************** Local Functions ************************/
-
- void Get1Line(
- ColorSpec* line,
- void* pix,
- int size,
- ColorSpec* CT,
- int pixelSize){
- int i,r,g,b;
- unsigned long x;
- if (pixelSize==8) {
- unsigned char* PIX =((unsigned char*)pix);
- for (i=0;i<size;i++) {
- x=*PIX++;
- line++;
- *((double*)(line))=*((double*)(CT+x));
- line->value=0;
- }
- } else if (pixelSize==16) {
- unsigned short* PIX =((unsigned short*)pix);
- for (i=0;i<size;i++) {
- x=*PIX++;
- line++;
- r=((x & 0x7C00) << 1) | ((x & 0x7C00) >> 4) |
- ((x & 0x7C00) >> 9) | ((x & 0x7C00) >> 14);
- g=((x & 0x03E0) << 6) | ((x & 0x03E0) << 1) |
- ((x & 0x03E0) >> 4) | ((x & 0x03E0) >> 9);
- b=((x & 0x001F) << 11) | ((x & 0x001F) << 6) |
- ((x & 0x001F) << 1) | ((x & 0x001F) >> 4);
- line->value=0;
- line->rgb.red= (unsigned short)r;
- line->rgb.green=(unsigned short)g;
- line->rgb.blue= (unsigned short)b;
- }
- } else { //pixelSize not 8 or 16, so it must be 32
- unsigned long* PIX =((unsigned long*)pix);
- for (i=0;i<size;i++) {
- x=*PIX++;
- line++;
- r=((x & 0xFF0000) >> 8) | ((x & 0xFF0000) >> 16);
- g= (x & 0x00FF00) | ((x & 0x00FF00) >> 8);
- b= (x & 0x0000FF) | ((x & 0x0000FF) << 8);
- line->value=0;
- line->rgb.red= (unsigned short)r;
- line->rgb.green=(unsigned short)g;
- line->rgb.blue= (unsigned short)b;
- }
- }
- }
-
- void Copy2Bitmap(
- ColorSpec* P,
- unsigned char* bits,
- int size) {
- int i;
- P++;
- for (i=0;i<size;i++) {
- *bits = (unsigned char) (
- (P[0].value & 0x80) |
- (P[1].value & 0x40) |
- (P[2].value & 0x20) |
- (P[3].value & 0x10) |
- (P[4].value & 0x08) |
- (P[5].value & 0x04) |
- (P[6].value & 0x02) |
- (P[7].value & 0x01) );
- P+=8;
- bits++;
- }
- }
-
- void EdgeRedGreenBlue(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH) {
- int i;
- unsigned long delta,acc;
- for (i=0;i<size;i++) {
- P++;Q++;
- acc=(unsigned long)P->rgb.red-Q->rgb.red;
- acc*=acc;
- delta=(unsigned long)P->rgb.green-Q->rgb.green;
- delta*=delta;
- acc+=delta;
- if (acc<delta) {P->value=Q->value=-1;continue;}
- delta=(unsigned long)P->rgb.blue-Q->rgb.blue;
- delta*=delta;
- acc+=delta;
- if ((acc>=TH) || (acc<delta)) P->value=Q->value=-1;
- }
- }
-
- void EdgeGreenBlue(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH) {
- int i;
- unsigned long delta,acc;
- for (i=0;i<size;i++) {
- P++;Q++;
- acc=(unsigned long)P->rgb.green-Q->rgb.green;
- acc*=acc;
- delta=(unsigned long)P->rgb.blue-Q->rgb.blue;
- delta*=delta;
- acc+=delta;
- if ((acc>=TH) || (acc<delta)) P->value=Q->value=-1;
- }
- }
-
- void EdgeRedBlue(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH) {
- int i;
- unsigned long delta,acc;
- for (i=0;i<size;i++) {
- P++;Q++;
- acc=(unsigned long)P->rgb.red-Q->rgb.red;
- acc*=acc;
- delta=(unsigned long)P->rgb.blue-Q->rgb.blue;
- delta*=delta;
- acc+=delta;
- if ((acc>=TH) || (acc<delta)) P->value=Q->value=-1;
- }
- }
-
- void EdgeRedGreen(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH) {
- int i;
- unsigned long delta,acc;
- for (i=0;i<size;i++) {
- P++;Q++;
- acc=(unsigned long)P->rgb.red-Q->rgb.red;
- acc*=acc;
- delta=(unsigned long)P->rgb.green-Q->rgb.green;
- delta*=delta;
- acc+=delta;
- if ((acc>=TH) || (acc<delta)) P->value=Q->value=-1;
- }
- }
-
- void EdgeBlue(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH) {
- int i;
- unsigned long acc;
- for (i=0;i<size;i++) {
- P++;Q++;
- acc=(unsigned long)P->rgb.blue-Q->rgb.blue;
- acc*=acc;
- if (acc>=TH) P->value=Q->value=-1;
- }
- }
-
- void EdgeGreen(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH) {
- int i;
- unsigned long acc;
- for (i=0;i<size;i++) {
- P++;Q++;
- acc=(unsigned long)P->rgb.green-Q->rgb.green;
- acc*=acc;
- if (acc>=TH) P->value=Q->value=-1;;
- }
- }
-
- void EdgeRed(
- ColorSpec* P,
- ColorSpec* Q,
- int size,
- unsigned long TH) {
- int i;
- unsigned long acc;
- for (i=0;i<size;i++) {
- P++;Q++;
- acc=(unsigned long)P->rgb.red-Q->rgb.red;
- acc*=acc;
- if (acc>=TH) P->value=Q->value=-1;
- }
- }
-